package org.example.dp.bidimensional;

import java.util.Arrays;

/**
 * @Description: TODO
 * @Author wyatt
 * @Data 2024/05/10 18:20
 */

//给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
//
// 两个相邻元素间的距离为 1 。
//
//
//
// 示例 1：
//
//
//
//
//输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
//输出：[[0,0,0],[0,1,0],[0,0,0]]
//
//
// 示例 2：
//
//
//
//
//输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
//输出：[[0,0,0],[0,1,0],[1,2,1]]
//
//
//
//
// 提示：
//
//
// m == mat.length
// n == mat[i].length
// 1 <= m, n <= 10⁴
// 1 <= m * n <= 10⁴
// mat[i][j] is either 0 or 1.
// mat 中至少有一个 0
//
//
// Related Topics 广度优先搜索 数组 动态规划 矩阵 👍 927 👎 0


public class Solution542 {

    public static void main(String[] args) {

        int[][] array = {
                {0, 0, 0},
                {0, 1, 0},
                {1, 1, 1}
        };

        Solution542 solution = new Solution542();
        int[][] result = solution.updateMatrix(array);

        for (int i = 0; i < result.length; i++) {
            for (int j = 0; j < result[i].length; j++) {
                System.out.print(result[i][j] + " ");
            }
            System.out.println(); // 每行结束后换行
        }
    }

    public int[][] updateMatrix(int[][] mat) {

        int[][] dp = new int[mat.length][mat[0].length];

        //初始化默认值， 默认最大值
        for(int i=0;i<dp.length;i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }

        //两次动态搜索，第一次 左上角
        for(int i=0;i<mat.length;i++) {
            for (int j = 0; j < mat[i].length; j++) {

                if(mat[i][j] == 0){
                    dp[i][j] = 0;
                } else {
                    if(i>0){
                        dp[i][j] = Math.min(dp[i-1][j] + 1, dp[i][j]);
                    }

                    if(j>0){
                        dp[i][j] = Math.min(dp[i-1][j] + 1, dp[i][j]);
                    }
                }
            }
        }

        //两次动态搜索，第一次 右下角

        for(int i=mat.length-1;i>0;i--) {
            for (int j = mat[i].length-1; j > 0; j--) {
                if(dp[i][j] != 0){
                    if( i< mat.length-1){
                        dp[i][j] = Math.min(dp[i+1][j] + 1, dp[i][j]);
                    }

                    if(j< mat[i].length-1){
                        dp[i][j] = Math.min(dp[i][j+1] + 1, dp[i][j]);
                    }
                }
            }
        }

        return dp;
    }

}
